πŸ’‘ 졜μž₯ 증가 μˆ˜μ—΄(LIS)

@Seongukbaek Posted May 09, 2022 Β· Updated May 09, 2022 Β· 3 min read

🧷 졜μž₯ 증가 μˆ˜μ—΄

κ°€μž₯ κΈ΄ μ¦κ°€ν•˜λŠ” λΆ€λΆ„ μˆ˜μ—΄(Longest Increasing Sequence)둜, μΌλ°˜μ μœΌλ‘œλŠ” DPλ₯Ό μ΄μš©ν•΄ ν•΄κ²°ν•œλ‹€.

{7, 2, 3, 8, 4, 5} -> LIS -> {2, 3, 4, 5}

πŸͺš DPλ₯Ό ν™œμš©ν•œ κ΅¬ν˜„ 및 μ‹œκ°„ λ³΅μž‘λ„

int[] arr = {7, 2, 3, 8, 4, 5}; int[] dp = new int[arr.length]; // LIS μ €μž₯ λ°°μ—΄ int max = 0; for (int i = 1; i < dp.length; i++) { for (int j = i - 1; j >= 0; j--) { if (arr[i] > arr[j]) { dp[i] = (dp[i] < dp[j] + 1) ? dp[j] + 1 : dp[i]; if (max < dp[i]) max = dp[i]; } } } int[] answer = new int[max + 1]; int check = dp[dp.length - 1]; for (int i = dp.length - 1; i >= 0; i--) { if (dp[i] == check) { answer[check] = arr[i]; check--; } } // DP에 μ €μž₯된 κ°’ 쀑 μ΅œλŒ“κ°’ + 1이 LIS의 길이 System.out.println(Arrays.toString(answer));

ν•˜μ§€λ§Œ μœ„μ™€ 같이 DPλ₯Ό ν™œμš©ν•˜λŠ” λ°©μ‹μ˜ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(N2)O(N^2)이닀.

이λ₯Ό μ€„μ΄λŠ” 쒋은 방법은 이뢄 탐색을 ν™œμš©ν•˜λŠ” 것이닀.

πŸͺš 이뢄 탐색을 ν™œμš©ν•œ κ΅¬ν˜„ 및 μ‹œκ°„ λ³΅μž‘λ„

LISλ₯Ό ꡬ성할 λ•Œ 이뢄 탐색을 ν™œμš©ν•œλ‹€.

  • LIS의 ν˜•νƒœλ₯Ό μœ μ§€ν•˜κΈ° μœ„ν•΄ μ£Όμ–΄μ§„ λ°°μ—΄μ˜ 인덱슀λ₯Ό ν•˜λ‚˜μ”© μ‚΄νŽ΄λ³Έλ‹€.
  • ν•΄λ‹Ή μˆ«μžκ°€ λ“€μ–΄κ°ˆ μœ„μΉ˜λ₯Ό 이뢄 νƒμƒ‰μœΌλ‘œ 탐색해 μ‚½μž…ν•œλ‹€.

일반적으둜 이뢄 νƒμƒ‰μ˜ μ‹œκ°„ λ³΅μž‘λ„λŠ” O(logN)O(logN)이닀. λ”°λΌμ„œ 이λ₯Ό μ΄μš©ν•΄ μ‹œκ°„ λ³΅μž‘λ„λ₯Ό O(NlogN)O(NlogN) 으둜 쀄일 수 μžˆλ‹€.

static int[] arr = {7, 2, 3, 8, 4, 5}; static ArrayList<Integer> lis = new ArrayList<>(); public static void main(String[] args) { lis.add(arr[0]); int idx = 1; int j = 0; while(idx < arr.length) { if (lis.get(j) < arr[idx]) { lis.add(arr[idx]); j++; } else { lis.remove(j); lis.add(binarySearch(j, arr[idx]), arr[idx]); } idx++; } System.out.println(j + 1); System.out.println(lis); } private static int binarySearch(int right, int target) { // 항상 leftλŠ” μ‹œμž‘μ  int left = 0; int mid; while(left < right) { mid = (left + right) / 2; if (lis.get(left) < target) left = mid + 1; else right = mid; } return right; }

πŸ“• μ°Έκ³ 

@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€